"""
Problem 21: https://projecteuler.net/problem=21

Amicable Numbers

Let d(n) be defined as the sum of proper divisors of n (numbers less than n
which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and
each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55
and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and
142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.
"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = Thonny Python3.8.3
@creat_time = 2022/5/8
'''


def sumProperDivisors(n: int) -> int:
    '''
    >>> assert sumProperDivisors(220) == 284 and sumProperDivisors(284) == 220
    '''
    if n <= 1:
        return 0
    
    import math
    n_sqrt = int(math.sqrt(n))
    
    res = 1
    for i in range(2, n_sqrt + 1):
        d,m = divmod(n,i)
        if m:
            continue
        else:
            res += i + d
    
    if n_sqrt ** 2 == n:
        res -= n_sqrt
    
    return res

def isAmicableNumber(n: int) -> bool :
    '''
    >>> assert sumProperDivisors(284)
    '''
    spd_n = sumProperDivisors(n)
    return n != spd_n and sumProperDivisors(spd_n) == n

def solution(maxNum: int = 10000) -> int:
    '''
    Evaluate the sum of all the amicable numbers under 10000.
    '''
    res = 0
    
    for i in range(1, maxNum+1):
        spd_i = sumProperDivisors(i)        
        if spd_i != i and spd_i <= maxNum and sumProperDivisors(spd_i) == i:
            res += i
            print('amicable pair',i,spd_i)
    
    return res//2
    



if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose = False)
    
    print(solution())
    '''
    amicable pair 220 284
    amicable pair 284 220
    amicable pair 1184 1210
    amicable pair 1210 1184
    amicable pair 2620 2924
    amicable pair 2924 2620
    amicable pair 5020 5564
    amicable pair 5564 5020
    amicable pair 6232 6368
    amicable pair 6368 6232
    15813
    '''
    
    
    
    


    


